package bTree.LeetCode;

import java.util.Arrays;

public class 环形子数组的最大和 {
    public int maxSubarraySumCircular(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        if (max<=0){
            return max;
        }
        int sum = Arrays.stream(nums).sum();
        //1.不跨越的情况，直接求最大和
        int length = nums.length;
        int []dpMax=new int[length];
        dpMax[0]=nums[0];
        //2.跨越的情况就求中间的最小的
        int []dpMin=new int[length];
        dpMin[0]=nums[0];
        int res=Integer.MIN_VALUE;
        for (int i=1;i<length;i++){
            dpMax[i]=Math.max(dpMax[i-1]+nums[i],nums[i]);
            dpMin[i]=Math.min(dpMin[i-1]+nums[i],nums[i]);
            res=Math.max(res,dpMax[i]);
            res=Math.max(res,sum-dpMin[i]);
        }
   return res;
    }
}